package com.example.singlelinkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {

        //加入到链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(new HeroNode(1, "孙伟帅1", "帅哥"));
        singleLinkedList.addByOrder(new HeroNode(2, "孙伟帅2", "帅哥2"));
        singleLinkedList.addByOrder(new HeroNode(4, "孙伟帅4", "帅哥4"));
        singleLinkedList.addByOrder(new HeroNode(3, "孙伟帅3", "帅哥3"));
        singleLinkedList.addByOrder(new HeroNode(3, "孙伟帅3", "帅哥3"));
        singleLinkedList.addByOrder(new HeroNode(7, "孙伟帅7", "帅哥7"));
        singleLinkedList.addByOrder(new HeroNode(11, "孙伟帅11", "帅哥11"));
        singleLinkedList.addByOrder(new HeroNode(15, "孙伟帅15", "帅哥15"));
        //显示一把，
        System.out.println("--------------原来-----------");
        singleLinkedList.list();
        /*//测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "王麒麟~~");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况");
        singleLinkedList.list();*/
        /*//删除
        System.out.println("--------------删除--------------");
        singleLinkedList.delete(2);
        singleLinkedList.delete(1);
        singleLinkedList.delete(3);
        singleLinkedList.delete(4);
        singleLinkedList.list();*/
        //节点个数
//        System.out.println(singleLinkedList.getLength(singleLinkedList.getHead()));
        /*System.out.println(SingleLinkedList.getLength(singleLinkedList.getHead()));
        HeroNode lastIndexNode = SingleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 3);
        System.out.println(lastIndexNode);*/
//        System.out.println("反转后-----------------");
//        singleLinkedList.reversetList();
//        singleLinkedList.reversetList();
        System.out.println("反向打印-------------");
//        singleLinkedList.ReverseList();
        singleLinkedList.reversePrint(singleLinkedList.getHead());
    }
}

//定义一个节点，每个HeroNode对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;//指向下一个节点

    //构造方法，创建类的时候，就会执行
    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName+
                '}';
    }
}

//定义SingleLinkedList管理我们的英雄
class SingleLinkedList {
    //先初始化一个节点，头节点不要动，不存放具体数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    /**
     * 添加节点到单向链表
     * 思路：当不考虑编号顺序时
     * 1.找到当前链表的最后一个节点
     * 2.将最后这个节点的next 指向新的节点
     */
    public void add(HeroNode heroNode) {
        //因为head的节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //循环遍历，找到最后
        while (true) {
            //找到最后一个链表
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后，将temp后移
            temp = temp.next;//为temp.next赋值
        }
        //当退出while循环时，temp就指向了链表的最后
        //见最后这个节点的next指向新的节点
        temp.next = heroNode;
    }

    //显示链表【遍历】
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            //TODO：
            System.out.println("链表为空");
            return;
        }
        //TODO：因为头节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp.name);
            //将temp后移，一点记住，不然死循环
            temp = temp.next;
        }

    }

    /**
     * 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
     * 如果有这个排名，则添加失败并给出提示
     */
    public void addByOrder(HeroNode heroNode) {
        /**
         * 因为头结点不能动，因此我们仍然通过一个辅助指针（变量）来帮助我们找到添加的位置
         * 单链表，因为我们找的temp是位于添加位置的前一个节点，否则就插入不了
         */
        HeroNode temp = head;
        boolean flag = false;//flag标志添加的编号是否存在，默认为false
        while (true) {
            if (temp.next == null) {//说明已经遍历到最后一个
                break;
            }
            if (temp.next.no > heroNode.no) {//位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已经存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移，遍历当前的链表
        }
        //判断flag的值
        if (flag) {
            System.out.println("插入的已经存在");
        } else {
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //根据newHeroNode的no来修改即可
    public void update(HeroNode newHeroNode) {
        //判断现有链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        /**
         * 找到需要修改的节点，根据no编码
         * 定义一个辅助变量
         */
        HeroNode temp = head.next;
        //标记表示是否找到这个节点，默认为false，没有找到
        boolean flag = false;
        /**
         * 对全部的数据进行遍历
         */
        while (true) {
            if (temp == null) {
                //已经遍历完这个链表
                break;
            }
            if (temp.no == newHeroNode.no) {
                //找到
                flag = true;
                break;
            }
            //没有找到，赋值为下一个，继续找
            temp = temp.next;
        }
        //根据flag 判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {//没有找到
            System.out.println("不存在这个编号");
        }

    }

    //根据id来删除节点
    public void delete(int no) {
        HeroNode temp = this.head;
        boolean flag = false;
        while (true) {
            //表示遍历完，没有的时候也算遍历完
            if (temp.next == null) {
                System.out.println("遍历完了");
                break;
            }
            //找到就把flag设置为false
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;//后移继续遍历
        }
        //表示找到了对应删除的位置
        if (flag) {
            //这里所以到下一个后，中间那个就没有可达了，就会被gc回收
            temp.next = temp.next.next;
        }
        //没有找到对应删除的位置
        else {
            System.out.println("没有找到对应的位置哦");
        }
    }
    //获取单链表的节点的个数（如果是带头节点的链表，需求不统计头节点）

    /**
     * @param head 链表的头节点
     * @return 链表的节点个数
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        //标记值，0
        int length = 0;
        //定义一个辅助变量，这里我们没有提及头节点
        /*HeroNode cur = head.next;
        while (cur == null) {
            length++;
            cur=cur.next;
        }*/
//        return length;
        while (true) {
            if (head.next == null) {
                return length;
            }
            length++;
            head = head.next;
        }
    }

    /**
     * 查找单链表中的倒数第K个节点
     *
     * @param head  头节点
     * @param index 第几个的位置
     * @return 返回 倒数的第几个位置的HeroNode
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        //判断如果链表为空，返回null
        if (head.next == null) {
            return null;//没有找到
        }
        //第一个遍历得到链表的长度
        int size = getLength(head);
        //第二次遍历 size-index位置，就是我们倒数的第K个节点
        //先做一个index的效验
        if (index <= 0 || index > size) {
            return null;
        }
        //定义给辅助变量,for循环定位到倒数的index
        HeroNode cur = head.next;//3-1=2;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        // FIXME: 2021/2/6
        return cur;
    }

    //链表反转
    public void inversion() {
        /**
         * 一.判断是否为空链表或者链表的长度为1，如果是就直接退出，不用遍历
         */
        //标记头节点
        HeroNode temp = this.head;
        if (temp == null || temp.next == null) {
            System.out.println("此链表为空或者长度为一，无需反转");
            return;
        }
        //创建一个辅助节点
        HeroNode heroNodeHelper = new HeroNode(0, "", "");
        /**
         * 二.对节点进行遍历，到最后一个
         * 倒数第二个的next就是最后一个
         */
        //获取到倒数第2个，长度-1
        //创建一个节点帮助的辅助
        HeroNode heroNodeHelperTemp = heroNodeHelper;
        for (int i = getLength(getHead()); i >0; i--) {
            HeroNode indexNode = getIndexSecondToLast(i-1);//获取倒数第二个
            heroNodeHelperTemp.next=indexNode.next;//让最后一个等于辅助的第一个
            indexNode.next=null;//让倒数第二个的next置空
            heroNodeHelperTemp=heroNodeHelperTemp.next;//后移
        }
        head.next=heroNodeHelper.next;
    }
    private HeroNode getIndexSecondToLast(int length) {
        HeroNode temp = this.head;
        if (temp.next==null) {
            System.out.println("这个链表为空");
            //这个链表没有长度
            return null;
        }

        for (int i = 0; i < length; i++) {
            temp=temp.next;
        }
        return temp;
    }
    //链表反转2
    public void reversetList(){
        //如果链表为空或者只有一个节点，无需反转，直接返回
        if (head.next==null||head.next.next==null) {
            return;
        }
        //定义一个辅助指针，帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next=null;//指向当前节点【cur】的下一个节点
        HeroNode reverseHead=new HeroNode(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在行的链表reverseHead的最前端
        if (cur!=null) {
            next=cur.next;//先保存当前节点的下一个节点，因为后面需要使用
            cur.next=reverseHead.next;//将cur的下一个节点指向性的链表的最前端
            reverseHead.next=cur;
            cur=next;//让cur后移
        }
        //将head。next指向reverseHead.next,实现单链表反转
        head.next=reverseHead.next;
    }
    //链表反向遍历，要求不改变原来的结构
    public void ReverseList(){
        //判断是否为空链表，或者链表的长度只有一的话，直接返回
        if (head.next==null||head.next.next==null) {
            System.out.println("链表的长度空或长度为一");
            return;
        }
        //遍历链表并且打印
        for (int i = getLength(getHead()); i >0; i--) {
            //获取倒数第一个并且打印
            System.out.println(getIndexSecondToLast(i));
        }
    }
    public void reversePrint(HeroNode head){
        //先判断链表是否为空或者链表的长度为一，这样都不用去反向打印
        if (head.next==null||head.next.next==null) {
            System.out.println("长度为一或者长度为空，无需反转");
            return;
        }
        /**
         * 先把链表压入到栈中
         */
        HeroNode temp = head;
        Stack<HeroNode> heroNodes = new Stack<HeroNode>();//创建一个heroNode类型的栈
        while (true){
            //判断是否为最后一个链表，如果是就返回出去
            if (temp.next==null) {
                System.out.println("表示遍历到最后一个，即链表已经遍历完了");
                break;
            }
            heroNodes.push(temp.next);//压入到栈
            //后移
            temp=temp.next;
        }

        /**
         * 遍历打印出栈的内容
         */
        while (heroNodes.size() > 0) {
            System.out.println(heroNodes.pop());
        }
    }

}
/*
思路都是给一个辅助值，来进行问题的解决
 */

